package LimitedTimeGame.Day_0223;

/**
 * @author zxc
 * @date 2023/02/23 12:01
 **/

/**
 * 题目 ：将字符串拆解成递减的连续值
 * 题目详述 ：
 * 给你一个仅由数字组成的字符串 s 。
 * 请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的 数值 按 降序 排列，且每两个 相邻子字符串 的数值之 差 等于 1 。
 * 例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为 [90,89] 。
 * 这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
 * 另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。
 * 然而，所有这些拆分方法都不可行，因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。
 * 如果可以按要求拆分 s ，返回 true ；否则，返回 false 。
 * 子字符串 是字符串中的一个连续字符序列。
 *
 * 提示：
 * 1 <= s.length <= 20
 * s 仅由数字组成
 *
 */
public class SplitString {
    public static void main(String[] args) {
        System.out.println(splitString("200100"));
    }
    /**
     * 思路 ：
     * 即，首先 截取某段字符串来确定第一个数的值n，去后面字符串中寻找递减连续值n-1;
     * （1）若是找到连续值（n-1）的话，则继续向下遍历比较，直至到达字符串尾部;
     *  若是到达字符串尾部都是符合条件的话，则直接返回true即可;
     * （2）若是未能够找到连续值（n-1）的话，则重新截取与之前数值不一样的字符串，来进行比较遍历;
     * ===>
     * 若是遍历完全部可能性，未能够找到可能递减连续值的话，则代表不存在递减连续值;
     * @param s
     * @return
     */
    public static boolean splitString(String s) {
        int len = s.length();
        // 遍历第一个数字的所有可能情况
        for(int i = 1 ; i < len ; i++){
            Long value = Long.valueOf(s.substring(0, i));
            //特殊情况 ：若是第一个数字为0，则不可能构成递减连续数
            if(value == 0){
                continue;
            }
            // 递归遍历 当第一个数字为n时，后面字符串所构成的数字集是否能够组成递减连续数
            if(isDecreasing(s , i , len , value - 1)){
                return true;
            }
            // 为防止long类型所存储的数据直接溢出;
            // 若是当前遍历值value 比字符串中所能够组成的值大一位的话，即直接退出循环即可
            if(value.toString().length() > len - i){
                break;
            }
        }
        return false;
    }
    // isDecreasing函数 ：即，用于获取是否后续字符串能够构成递减的连续数;
    // begin，代表后续字符串开始位置;len,代表字符串长度;value,代表所要求解的递减值value
    private static boolean isDecreasing(String s, int begin, int len, long value) {
        // 递归结束条件 ：递归完所有字符串，即代表了 该字符串能够构成 递减的连续数;
        if(begin == len){
            return true;
        }
        // 遍历后续字符串中是否存在符合递减条件的数字;
        for(int i = 1 ; i <= len - begin ; i++){
            Long val = Long.valueOf(s.substring(begin, begin + i));
            // 特殊情况 ：即，若是 当前val == 0 && 后续还有连续的0 出现的话，直接跳转到不为零出现为止 || 字符串结束为止
            if(i + 1 <= len - begin && val.equals(Long.valueOf(s.substring(begin, begin + i + 1)))){
                continue;
            }
            // 当前遍历的值已经大于value，后续继续遍历的值 必然是大于当前遍历的值;
            // 所以没必要继续遍历下去，直接退出循环即可;
            if(val > value){
                break;
            }
            // 若是存在 后续字符串中有数字n == value的话，则选择 递归继续向下遍历
            if(val == value){
                return isDecreasing(s , begin + i , len , value - 1);
            }
        }
        // 即，若是遍历完后续字符串 || 提前退出（不符合要求），代表了后续字符串中不存在与之前数字构成递减连续数的数字;
        return false;
    }
}
